package impl;

import anaydis.sort.SorterType;
import anaydis.sort.gui.SorterListener;
import com.sun.istack.internal.NotNull;
import impl.*;

import java.util.Comparator;
import java.util.List;
import java.util.Locale;

/**
 * Created by IntelliJ IDEA.
 * User: Kevin Stessens
 * Date: 24/10/11
 * Time: 17:44
 * To change this template use File | Settings | File Templates.
 */
public class HeapSorter extends AbstractSorter {
    public HeapSorter() {
        super(SorterType.HEAP);
    }

    public <T> void sort(@NotNull Comparator<T> tComparator, @NotNull List<T> ts) {
        for (int i = ts.size() / 2; i >= 0; i--)
            subSort(tComparator, ts, i, ts.size());
        for (int i = ts.size() - 1; i > 0; i--) {
            swap(ts, 0, i);
            subSort(tComparator, ts, 0, i);
        }
    }

    public <T> void sort(Locale loc, @NotNull Comparator<T> tComparator, @NotNull List<T> ts) {
        for (int i = ts.size() / 2; i >= 0; i--)
            subSort(loc, tComparator, ts, i, ts.size());
        for (int i = ts.size() - 1; i > 0; i--) {
            swap(ts, 0, i);
            subSort(loc, tComparator, ts, 0, i);
        }
    }

    private static int leftChild(int i) {
        return 2 * i + 1;
    }

    private <T> void subSort(Comparator<T> tComparator, List<T> ts, int i, int n) {
        int child;

        for (ts.get(i); leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && greater(tComparator, ts, child + 1, (child)))
                child++;
            if (greater(tComparator, ts, child, i))
                swap(ts, i, child);
            else
                break;
        }
    }

    private <T> void subSort(Locale loc, Comparator<T> tComparator, List<T> ts, int i, int n) {
        int child;

        for (ts.get(i); leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && greater(loc, tComparator, ts, child + 1, (child)))
                child++;
            if (greater(loc, tComparator, ts, child, i))
                swap(ts, i, child);
            else
                break;
        }
    }


}
